//	--------------------------------------------------------------------
//	Copyright(C) 2006,2007 Zhao Yukun. All rights reserved.
//	This file is a part of the Xeres system.
//	Xeres 2007
//	Contact : xeres.engine@gmail.com
//	$(reservedInfo)
//	$(reservedDeclaration)
//	--------------------------------------------------------------------
///	@file	<dir_tree.inl>
///	@path	~/src/lib/utilities/
///	@date	2007/09/07
///	@desc	Director tree template.

#pragma once

#include "lib/utilities/debug.h"
#include "lib/utilities/dir_tree.h"

#define	DIRTREE_DEBUG		1

namespace xeres {

	// sub structure
	template< typename _Content > dir_tree< _Content >::dir_node::dir_node( void )
		: m_content()
		, m_parent( NULL )
	{
	}

	// copier
	template< typename _Content > dir_tree< _Content >::dir_node::dir_node( const dir_node& rhs )
		: m_content( rhs.m_content )
		, m_parent( rhs.m_parent )
		, m_name( rhs.m_name )
		, m_children( rhs.m_children )
	{
	}

	// open directory
	template< typename _Content > typename dir_tree< _Content >::dir_node *
		dir_tree< _Content >::dir_node::open_dir(
			const StringSeq& seq , int current , bool create_non_exist )
	{
		// determine if current directory is destination
		if( current == seq.size() )
		{
			assert( m_name == seq.back() );
			return this;
		}

		// get next dir
		const WString& sub = seq[ current ];

		dir_node * child = NULL;
		// match from children
		dict< WString , dir_node >::iterator it = m_children.find( sub );
		if( it == m_children.end() )
		{
			if( !create_non_exist )
				return NULL;
			child = &( m_children[ sub ] = dir_node() );
			child->m_name = sub;
			child->m_parent = this;
		}
		else
		{
			child = &( it->second );
		}
		return child->open_dir( seq , current + 1 , create_non_exist );
	}

	// open directory
	template< typename _Content > typename dir_tree< _Content >::dir_node *
		dir_tree< _Content >::dir_node::open_dir(
			const StringSeq& seq , int current , std::vector< iterator >& tree ,
			bool create_non_exist )
	{
		// determine if current directory is destination
		if( current == seq.size() )
		{
			assert( m_name == seq.back() );
			return this;
		}

		// get next dir
		const WString& sub = seq[ current ];

		dir_node * child = NULL;
		// match from children
		dict< WString , dir_node >::iterator it = m_children.find( sub );
		if( it == m_children.end() )
		{
			if( !create_non_exist )
				return NULL;
			child = &( m_children[ sub ] = dir_node() );
			child->m_name = sub;
			child->m_parent = this;
		}
		else
		{
			child = &( it->second );
		}
		if( m_parent )
		{
			iterator iter;
			iter.m_parent = m_parent;
			iter.m_current = m_parent->m_children.find( m_name );
			iter.m_depth = current;
			tree.push_back( iter );
		}
		return child->open_dir( seq , current + 1 , tree , create_non_exist );
	}

	// open directory
	template< typename _Content > const typename dir_tree< _Content >::dir_node *
		dir_tree< _Content >::dir_node::open_dir( const StringSeq& seq , int current ) const
	{
		// determine if current directory is destination
		if( current == seq.size() )
		{
			assert( m_name == seq.back() );
			return this;
		}

		// get next dir
		const WString& sub = seq[ current ];

		const dir_node * child = NULL;
		// match from children
		dict< WString , dir_node >::const_iterator it = m_children.find( sub );
		if( it == m_children.end() )
		{
			return NULL;
		}
		else
		{
			child = &( it->second );
		}
		return child->open_dir( seq , current + 1 );
	}

	// delete child
	template< typename _Content > void dir_tree< _Content >::dir_node::del_child( dir_node * child )
	{
		dict< WString , dir_node >::iterator it = m_children.find( child->m_name );
		assert( it != m_children.end() );
		m_children.erase( it );
	}

	// open node
	template< typename _Content > _Content * dir_tree< _Content >::open_node(
		const WString& path , bool create_non_exist )
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );

		dir_node * sec = m_root.open_dir( seq , 0 , create_non_exist );
		if( sec == NULL )
			return NULL;

		return &( sec->m_content );
	}

	// open node
	template< typename _Content > _Content * dir_tree< _Content >::open_node(
		const WString& path , std::vector< iterator >& tree , bool create_non_exist )
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );

		std::vector< iterator > parents;

		dir_node * sec = m_root.open_dir( seq , 0 , parents , create_non_exist );
		if( sec == NULL )
			return NULL;

		for( size_t i = 0 ; i < parents.size() ; ++i )
		{
			tree.push_back( parents[i] );
		}

		return &( sec->m_content );
	}

	// open node
	template< typename _Content > const _Content * dir_tree< _Content >::open_node(
		const WString& path ) const
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );

		const dir_node * sec = m_root.open_dir( seq , 0 );
		if( sec == NULL )
			return NULL;

		return &( sec->m_content );
	}

	// open parent
	template< typename _Content > const _Content * dir_tree< _Content >::open_parent(
		const WString& path ) const
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );

		const dir_node * sec = m_root.open_dir( seq , 0 );
		if( sec == NULL )
			return NULL;

		return &( sec->m_parent->m_content );
	}

	// open parent
	template< typename _Content > bool dir_tree< _Content >::open_node_with_parent(
		const WString& path , _Content *& node , _Content *& parent )
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );

		dir_node * sec = m_root.open_dir( seq , 0 , false );
		if( sec == NULL )
			return false;

		node = &( sec->m_content);
		parent = &( sec->m_parent->m_content );
		return true;
	}

	// ctor
	template< typename _Content > dir_tree< _Content >::dir_tree( void )
	{
	}

	// dtor
	template< typename _Content > dir_tree< _Content >::~dir_tree( void )
	{
	}

	// del node
	template< typename _Content > bool dir_tree< _Content >::del_node( const WString& path )
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );
		dir_node * sec = m_root.open_dir( seq , 0 , false );

		if( sec == NULL )
		{
			TRACE_ERROR( _S("dir_tree::del_node: Node %s does not exist.") , path.c_str() );
			return false;
		}
		sec->m_parent->del_child( sec );
		return true;
	}

	// clear all nodes
	template< typename _Content > void dir_tree< _Content >::clear( void )
	{
		m_root.m_children.clear();
	}
	
	// return if tree is empty
	template< typename _Content > bool dir_tree< _Content >::empty( void ) const
	{
		return m_root.m_children.empty();
	}

	// list dir
	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const WString& path , std::vector< WString >& result ) const
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );
		const dir_node * sec = m_root.open_dir( seq , 0 );
		if( sec == NULL )
			return false;

		for( dict< WString , dir_node >::const_iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			result.push_back( it->first );
		}
		return true;
	}

	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const WString& path , dict< WString , _Content >& result ) const
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );
		const dir_node * sec = m_root.open_dir( seq , 0 );
		if( sec == NULL )
			return false;

		for( dict< WString , dir_node >::const_iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			result[ it->first ] = it->second.m_content;
		}
		return true;
	}

	// list dir
	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const WString& path , std::vector< _Content >& result ) const
	{
		// break into seq
		StringSeq seq;
		break_string( path , '/' , seq , false );
		const dir_node * sec = m_root.open_dir( seq , 0 );
		if( sec == NULL )
			return false;

		for( dict< WString , dir_node >::const_iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			result.push_back( it->second.m_content );
		}
		return true;
	}


	// list dir
	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const iterator& node , std::vector< WString >& result ) const
	{
		for( dict< WString , dir_node >::const_iterator it = m_root.m_children.begin() ;
			it != m_root.m_children.end() ; ++it )
		{
			result.push_back( it->first );
		}
		return true;
	}

	// list dir
	template< typename _Content > void dir_tree< _Content >::list_root( std::vector< WString >& result ) const
	{
		for( dict< WString , dir_node >::const_iterator it = m_root.m_children.begin() ;
			it != m_root.m_children.end() ; ++it )
		{
			result.push_back( it->first );
		}
	}

	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const iterator& node , dict< WString , _Content >& result ) const
	{
		if( node == end() )
			return false;

		const dir_node * sec = &(node.m_current->second);
		for( dict< WString , dir_node >::const_iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			result[ it->first ] = it->second.m_content;
		}
		return true;
	}

	template< typename _Content > void dir_tree< _Content >::list_root( dict< WString , _Content >& result ) const
	{
		for( dict< WString , dir_node >::const_iterator it = m_root.m_children.begin() ;
			it != m_root.m_children.end() ; ++it )
		{
			result[ it->first ] = it->second.m_content;
		}
	}

	// list dir
	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const iterator& node , std::vector< _Content >& result ) const
	{
		if( node == end() )
			return false;
		
		const dir_node * sec = &(node.m_current->second);

		for( dict< WString , dir_node >::const_iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			result.push_back( it->second.m_content );
		}
		return true;
	}

	// list dir
	template< typename _Content > void dir_tree< _Content >::list_root( std::vector< _Content >& result ) const
	{
		for( dict< WString , dir_node >::const_iterator it = m_root.m_children.begin() ;
			it != m_root.m_children.end() ; ++it )
		{
			result.push_back( it->second.m_content );
		}
	}

	// list dir
	template< typename _Content > bool dir_tree< _Content >::list_dir(
		const iterator& node , std::vector< iterator >& result )
	{
		if( node == end() )
			return false;

		dir_node * sec = &(node.m_current->second);

		for( dict< WString , dir_node >::iterator it = sec->m_children.begin() ;
			it != sec->m_children.end() ; ++it )
		{
			DirIter iter;
			iter.m_current = it;
			iter.m_parent = sec;
			iter.m_depth = node.m_depth + 1;
			result.push_back( iter );
		}
		return true;
	}

	// list dir
	template< typename _Content > void dir_tree< _Content >::list_root( std::vector< iterator >& result )
	{
		for( dict< WString , dir_node >::iterator it = m_root.m_children.begin() ;
			it != m_root.m_children.end() ; ++it )
		{
			DirIter iter;
			iter.m_current = it;
			iter.m_parent = &m_root;
			iter.m_depth = 0;
			result.push_back( iter );
		}
	}

	// iterator
	template< typename _Content > typename dir_tree< _Content >::iterator
		dir_tree< _Content >::begin( void )
	{
		DirIter it;
		it.m_current = m_root.m_children.begin();
		it.m_parent = &m_root;
		it.m_depth = 0;
		return it;
	}

	// iterator
	template< typename _Content > typename dir_tree< _Content >::iterator
		dir_tree< _Content >::end( void )
	{
		DirIter it;
		it.m_current = m_root.m_children.end();
		it.m_parent = &m_root;
		it.m_depth = 0;
		return it;
	}

	// operator ++
	template< typename _Content > typename dir_tree< _Content >::DirIter&
		dir_tree< _Content >::DirIter::next( void )
	{
		// see if I have any children
		if( m_current->second.m_children.size() > 0 )
		{
			// step in
			m_parent = &(m_current->second);
			m_current = m_current->second.m_children.begin();
			++m_depth;
			return *this;
		}

		// step in next
		while( ++m_current == m_parent->m_children.end() )
		{
			// root.end()
			if( m_depth == 0 )
			{
				return *this;
			}
			dir_node * node = m_parent;
			m_parent = m_parent->m_parent;
			m_current = m_parent->m_children.find( node->m_name );
			--m_depth;
		}
		return *this;
	}

	// depth
	template< typename _Content > int dir_tree< _Content >::DirIter::depth( void ) const
	{
		return m_depth;
	}

	// content
	template< typename _Content > const WString& dir_tree< _Content >::DirIter::name( void ) const
	{
		return m_current->second.m_name;
	}

	// content
	template< typename _Content > _Content& dir_tree< _Content >::DirIter::content( void )
	{
		return m_current->second.m_content;
	}

	template< typename _Content > const _Content& dir_tree< _Content >::DirIter::content( void ) const
	{
		return m_current->second.m_content;
	}

	// next
	template< typename _Content > typename dir_tree< _Content >::DirIter&
		dir_tree< _Content >::DirIter::operator ++ ( void )
	{
		return next();
	}

	// content
	template< typename _Content > _Content& dir_tree< _Content >::DirIter::operator * ( void )
	{
		return content();
	}

	template< typename _Content > const _Content& dir_tree< _Content >::DirIter::operator * ( void ) const
	{
		return content();
	}

	// comparison
	template< typename _Content > bool dir_tree< _Content >::DirIter::operator == ( const DirIter& iter ) const
	{
		return m_parent == iter.m_parent && m_current == iter.m_current;
	}

	template< typename _Content > bool dir_tree< _Content >::DirIter::operator != ( const DirIter& iter ) const
	{
		return m_parent != iter.m_parent || m_current != iter.m_current;
	}

} // namespace xeres
